<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us" lang="en-us">
<head>
  <link href="//gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta name="generator" content="Hugo 0.68.3" />

  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">

  <title>python数据结构----散列表(哈希表) &middot; 我的博客</title>

  
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/print.css" media="print">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/poole.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/syntax.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/hyde.css">
    <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Abril+Fatface|PT+Sans:400,400i,700">


  
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/apple-touch-icon-144-precomposed.png">
  <link rel="shortcut icon" href="/favicon.png">

  
  
</head>

  <body class="theme-base-0b ">
  <aside class="sidebar">
  <div class="container sidebar-sticky">
    <div class="sidebar-about">
      <a href="/my_technology_blog/"><h1>我的博客</h1></a>
      <p class="lead">
       杨博的博客 
      </p>
    </div>

    <nav>
      <ul class="sidebar-nav">
        <li><a href="/my_technology_blog/">Home</a> </li>
        
      </ul>
    </nav>

    <p>&copy; 2021. All rights reserved. </p>
  </div>
</aside>

    <main class="content container">
    <div class="post">
  <h1>python数据结构----散列表(哈希表)</h1>
  <time datetime=2020-06-09T17:55:07&#43;0800 class="post-date">Tue, Jun 9, 2020</time>
  <h1 id="python数据结构散列表">[Python数据结构——散列表]</h1>
<p>散列表的实现常常叫做散列(hashing)。散列仅支持INSERT,SEARCH和DELETE操作，都是在常数平均时间执行的。需要元素间任何排序信息的操作将不会得到有效的支持。</p>
<p>散列表是普通数组概念的推广。如果空间允许，可以提供一个数组，为每个可能的关键字保留一个位置，就可以运用直接寻址技术。</p>
<p>当实际存储的关键字比可能的关键字总数较小时，采用散列表就比较直接寻址更为有效。在散列表中，不是直接把关键字用作数组下标，而是根据关键字计算出下标，这种</p>
<p>关键字与下标之间的映射就叫做散列函数。</p>
<h3 id="1散列函数">1.散列函数</h3>
<p>一个好的散列函数应满足简单移植散列的假设：每个关键字都等可能的散列到m个槽位的任何一个中去，并与其它的关键字已被散列到哪个槽位无关。</p>
<p><strong>1.1 通常散列表的关键字都是自然数。</strong></p>
<p><strong>1.11 除法散列法</strong></p>
<p>通过关键字k除以槽位m的余数来映射到某个槽位中。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">hash(k)<span style="color:#f92672">=</span>k mod m
</code></pre></div><p>应用除法散列时，应注意m的选择，m不应该是2的幂，通常选择与2的幂不太接近的质数。</p>
<p><strong>1.12 乘法散列法</strong></p>
<p>乘法方法包含两个步骤，第一步用关键字k乘上常数A(0&lt;A&lt;1),并取出小数部分，然后用m乘以这个值，再取结果的底(floor)。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">hash(k)<span style="color:#f92672">=</span>floor(m(kA mod <span style="color:#ae81ff">1</span>))
</code></pre></div><p>乘法的一个优点是对m的选择没有什么特别的要求，一般选择它为2的某个幂。</p>
<p>一般取A=(√5-1)/2=0.618比较理想。</p>
<p><strong>1.13 全域散列</strong></p>
<p>随机的选择散列函数，使之独立于要存储的关键字。在执行开始时，就从一族仔细设计的函数中，随机的选择一个作为散列函数，随机化保证了</p>
<p>没有哪一种输入会始终导致最坏情况发生。</p>
<p><strong>1.2 如果关键字是字符串，散列函数需要仔细的选择</strong></p>
<p><strong>1.2.1</strong> 将字符串中字符的ASCII码值相加</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">_hash</span>(key,m):
    hashVal<span style="color:#f92672">=</span><span style="color:#ae81ff">0</span>
    <span style="color:#66d9ef">for</span> _ <span style="color:#f92672">in</span> key:
        hashVal<span style="color:#f92672">+=</span>ord(_)
    <span style="color:#66d9ef">return</span> hashVal<span style="color:#f92672">%</span>m
</code></pre></div><p>由于ascii码最大127，当表很大时，函数不会很好的分配关键字。</p>
<p><strong>1.2.2</strong> 取关键字的前三个字符。</p>
<p>值27表示英文字母表的字母个数加上一个空格。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">hash(k)<span style="color:#f92672">=</span>k[<span style="color:#ae81ff">0</span>]<span style="color:#f92672">+</span><span style="color:#ae81ff">27</span><span style="color:#f92672">*</span>k[<span style="color:#ae81ff">1</span>]<span style="color:#f92672">+</span><span style="color:#ae81ff">729</span><span style="color:#f92672">*</span>k[<span style="color:#ae81ff">2</span>]
</code></pre></div><p><strong>1.2.3</strong> 用霍纳法则把所有字符扩展到n次多项式。</p>
<p>用32代替27，可以用于位运算。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">def</span> <span style="color:#a6e22e">_hash</span>(key,m):
    hashval<span style="color:#f92672">=</span><span style="color:#ae81ff">0</span>
    <span style="color:#66d9ef">for</span> _ <span style="color:#f92672">in</span> key:
        hashval<span style="color:#f92672">=</span>(hashval<span style="color:#f92672">&lt;&lt;</span><span style="color:#ae81ff">5</span>)<span style="color:#f92672">+</span>ord(_)
    <span style="color:#66d9ef">return</span> hashval<span style="color:#f92672">%</span>m
</code></pre></div><h3 id="2-分离链接法">2. 分离链接法</h3>
<p>散列表会面临一个问题，当两个关键字散列到同一个值的时候，称之为冲突或者碰撞(collision)。解决冲突的第一种方法通常叫做分离链接法(separate chaining)。</p>
<p>其做法是将散列到同一个值的所有元素保留到一个链表中，槽中保留一个指向链表头的指针。</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Chaxi.jpg" alt=""></p>
<p>为执行FIND，使用散列函数来确定要考察哪个表，遍历该表并返回关键字所在的位置。</p>
<p>为执行INSERT，首先确定该元素是否在表中。如果是新元素，插入表的前端或末尾。</p>
<p>为执行DELETE，找到该元素执行链表删除即可。</p>
<p>散列表中元素个数与散列表大小的比值称之为装填因子(load factor)λ。</p>
<p>执行一次不成功的查找，遍历的链接数平均为λ，成功的查找则花费1+(λ/2)。</p>
<p>分离链接散列的一般做法是使得λ尽量接近于1。</p>
<p>代码：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">_ListNode</span>(object):
    <span style="color:#66d9ef">def</span> __init__(self,key):
        self<span style="color:#f92672">.</span>key<span style="color:#f92672">=</span>key
        self<span style="color:#f92672">.</span>next<span style="color:#f92672">=</span>None
<span style="color:#66d9ef">class</span> <span style="color:#a6e22e">HashMap</span>(object):
    <span style="color:#66d9ef">def</span> __init__(self,tableSize):
        self<span style="color:#f92672">.</span>_table<span style="color:#f92672">=</span>[None]<span style="color:#f92672">*</span>tableSize
        self<span style="color:#f92672">.</span>_n<span style="color:#f92672">=</span><span style="color:#ae81ff">0</span>  <span style="color:#75715e">#number of nodes in the map</span>
    <span style="color:#66d9ef">def</span> __len__(self):
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>_n
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">_hash</span>(self,key):
        <span style="color:#66d9ef">return</span> abs(hash(key))<span style="color:#f92672">%</span>len(self<span style="color:#f92672">.</span>_table)
    <span style="color:#66d9ef">def</span> __getitem__(self,key):
        j<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_hash(key)
        node<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_table[j]
        <span style="color:#66d9ef">while</span> node <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None <span style="color:#f92672">and</span> node<span style="color:#f92672">.</span>key<span style="color:#f92672">!=</span>key :
            node<span style="color:#f92672">=</span>node<span style="color:#f92672">.</span>next
        <span style="color:#66d9ef">if</span> node <span style="color:#f92672">is</span> None:
            <span style="color:#66d9ef">raise</span> <span style="color:#a6e22e">KeyError</span>,<span style="color:#e6db74">&#39;KeyError&#39;</span><span style="color:#f92672">+</span>repr(key)
        <span style="color:#66d9ef">return</span> node       
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">insert</span>(self,key):
        <span style="color:#66d9ef">try</span>:
            self[key]
        <span style="color:#66d9ef">except</span> <span style="color:#a6e22e">KeyError</span>:
            j<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_hash(key)
            node<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_table[j]
            self<span style="color:#f92672">.</span>_table[j]<span style="color:#f92672">=</span>_ListNode(key)
            self<span style="color:#f92672">.</span>_table[j]<span style="color:#f92672">.</span>next<span style="color:#f92672">=</span>node
            self<span style="color:#f92672">.</span>_n<span style="color:#f92672">+=</span><span style="color:#ae81ff">1</span>
    <span style="color:#66d9ef">def</span> __delitem__(self,key):
        j<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_hash(key)
        node<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_table[j]
        <span style="color:#66d9ef">if</span> node <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None:
            <span style="color:#66d9ef">if</span> node<span style="color:#f92672">.</span>key<span style="color:#f92672">==</span>key:
                self<span style="color:#f92672">.</span>_table[j]<span style="color:#f92672">=</span>node<span style="color:#f92672">.</span>next
                self<span style="color:#f92672">.</span>_<span style="color:#f92672">-=</span><span style="color:#ae81ff">1</span>
            <span style="color:#66d9ef">else</span>:
                <span style="color:#66d9ef">while</span> node<span style="color:#f92672">.</span>next<span style="color:#f92672">!=</span>None:
                    pre<span style="color:#f92672">=</span>node
                    node<span style="color:#f92672">=</span>node<span style="color:#f92672">.</span>next
                    <span style="color:#66d9ef">if</span> node<span style="color:#f92672">.</span>key<span style="color:#f92672">==</span>key:
                        pre<span style="color:#f92672">.</span>next<span style="color:#f92672">=</span>node<span style="color:#f92672">.</span>next
                        self<span style="color:#f92672">.</span>_n<span style="color:#f92672">-=</span><span style="color:#ae81ff">1</span>
                        <span style="color:#66d9ef">break</span>
</code></pre></div><h3 id="3开放定址法">3.开放定址法</h3>
<p>在开放定址散列算法中，如果有冲突发生，那么就要尝试选择另外的单元，直到找出空的单元为止。</p>
<p>h(k，i)=(h&rsquo;(k)+f(i)) mod m，i=0,1,&hellip;,m-1  ,其中f(0)=0</p>
<p><strong>3.1 线性探测法</strong></p>
<p>函数f(i)是i的线性函数</p>
<p>h(k，i)=(h&rsquo;(k)+i) mod m</p>
<p>相当于逐个探测每个单元</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Chaxi3.1.jpg" alt="img"></p>
<p>线性探测会存在一个问题，称之为一次群集。随着被占用槽的增加，平均查找时间也会不断增加。当一个空槽前有i个满的槽时，该空槽为下一个将被占用</p>
<p>槽的概率是(i+1)/m。连续被占用槽的序列会越来越长，平均查找时间也会随之增加。</p>
<p>如果表有一半多被填满的话，线性探测不是个好办法。</p>
<p><strong>3.2 平法探测</strong></p>
<p>平方探测可以取消线性探测中的一次群集问题。</p>
<p>h(k，i)=(h&rsquo;(k)+c1i+c2i2) mod m</p>
<p>平方探测中，如果表的一半为空，并且表的大小是质数，保证能够插入一个新的元素。</p>
<p>平方探测会引起二次群集的问题。</p>
<p><strong>3.3 双散列</strong></p>
<p>双散列是用于开放定址法的最好方法之一。</p>
<p>h(k，i)=(h1(k)+ih2(k)) mod m</p>
<p>为能查找整个散列表，值h2(k)要与m互质。确保这个条件成立的一种方法是取m为2的幂，并设计一个总产生奇数的h2。另一种方法是取m为质数，并设计一个总是产生</p>
<p>较m小的正整数的h2。</p>
<p>例如取：</p>
<p>h1(k)=k mod m，h2(k)=1+(k mod m&rsquo;),m'为略小于m的整数。</p>
<p>给定一个装填因子λ的开放定址散列表，插入一个元素至多需要1/(1-λ)次探查。</p>
<p>给定一个装填因子λ&lt;1的开放定址散列表，一次成功查找中的期望探查数至多为(1/λ)ln(1/1-λ)。</p>
<h3 id="4--再散列">4.  再散列</h3>
<p>如果表的元素填得太满，那么操作的运行时间将开始消耗过长。一种解决方法是当表到达某个装填因子时，建立一个大约两倍大的表，而且使用一个相关的新散列函数，</p>
<p>扫描整个原始散列表，计算每个元素的新散列值并将其插入到新表中。</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Chaxi4.jpg" alt="img"></p>
<p>为避免开放定址散列查找错误，删除操作要采用懒惰删除。</p>
<p>代码</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">HashEntry</span>(object):
    <span style="color:#66d9ef">def</span> __init__(self,key,value):
        self<span style="color:#f92672">.</span>key<span style="color:#f92672">=</span>key
        self<span style="color:#f92672">.</span>value<span style="color:#f92672">=</span>value
<span style="color:#66d9ef">class</span> <span style="color:#a6e22e">HashTable</span>(object):
    _DELETED<span style="color:#f92672">=</span>HashEntry(None,None)  <span style="color:#75715e">#用于删除</span>
    <span style="color:#66d9ef">def</span> __init__(self,tablesize):
        self<span style="color:#f92672">.</span>_table<span style="color:#f92672">=</span>tablesize<span style="color:#f92672">*</span>[None]
        self<span style="color:#f92672">.</span>_n<span style="color:#f92672">=</span><span style="color:#ae81ff">0</span>
    <span style="color:#66d9ef">def</span> __len__(self):
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>_n
    <span style="color:#66d9ef">def</span> __getitem__(self,key):
        found,j<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_findSlot(key)
        <span style="color:#66d9ef">if</span> <span style="color:#f92672">not</span> found:
            <span style="color:#66d9ef">raise</span> <span style="color:#a6e22e">KeyError</span>
        <span style="color:#66d9ef">return</span> self<span style="color:#f92672">.</span>_table[j]<span style="color:#f92672">.</span>value
    <span style="color:#66d9ef">def</span> __setitem__(self,key,value):
        found,j<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_findSlot(key)
        <span style="color:#66d9ef">if</span> <span style="color:#f92672">not</span> found:
            self<span style="color:#f92672">.</span>_table[j]<span style="color:#f92672">=</span>HashEntry(key,value)
            self<span style="color:#f92672">.</span>_n<span style="color:#f92672">+=</span><span style="color:#ae81ff">1</span>
            <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>_n<span style="color:#f92672">&gt;</span>len(self<span style="color:#f92672">.</span>_table)<span style="color:#f92672">//</span><span style="color:#ae81ff">2</span>:
                self<span style="color:#f92672">.</span>_rehash()
        <span style="color:#66d9ef">else</span>:
            self<span style="color:#f92672">.</span>_table[j]<span style="color:#f92672">.</span>value<span style="color:#f92672">=</span>value
    <span style="color:#66d9ef">def</span> __delitem__(self,key):
        found,j<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_findSlot(key)
        <span style="color:#66d9ef">if</span> found:
            self<span style="color:#f92672">.</span>_table[j]<span style="color:#f92672">=</span>HashTable<span style="color:#f92672">.</span>_DELETED   <span style="color:#75715e"># 懒惰删除</span>
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">_rehash</span>(self):
        oldList<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_table
        newsize<span style="color:#f92672">=</span><span style="color:#ae81ff">2</span><span style="color:#f92672">*</span>len(self<span style="color:#f92672">.</span>_table)<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>
        self<span style="color:#f92672">.</span>_table<span style="color:#f92672">=</span>newsize<span style="color:#f92672">*</span>[None]
        self<span style="color:#f92672">.</span>_n<span style="color:#f92672">=</span><span style="color:#ae81ff">0</span>
        <span style="color:#66d9ef">for</span> entry <span style="color:#f92672">in</span> oldList:
            <span style="color:#66d9ef">if</span> entry <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> None <span style="color:#f92672">and</span> entry <span style="color:#f92672">is</span> <span style="color:#f92672">not</span> HashTable<span style="color:#f92672">.</span>_DELETED:
                self[entry<span style="color:#f92672">.</span>key]<span style="color:#f92672">=</span>entry<span style="color:#f92672">.</span>value
                self<span style="color:#f92672">.</span>_n<span style="color:#f92672">+=</span><span style="color:#ae81ff">1</span>           
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">_findSlot</span>(self,key):
        slot<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_hash1(key)
        step<span style="color:#f92672">=</span>self<span style="color:#f92672">.</span>_hash2(key)
        firstSlot<span style="color:#f92672">=</span>None
        <span style="color:#66d9ef">while</span> True:
            <span style="color:#66d9ef">if</span> self<span style="color:#f92672">.</span>_table[slot] <span style="color:#f92672">is</span> None:
                <span style="color:#66d9ef">if</span> firstSlot <span style="color:#f92672">is</span> None:
                    firstSlot<span style="color:#f92672">=</span>slot
                <span style="color:#66d9ef">return</span> (False,firstSlot)
            <span style="color:#66d9ef">elif</span> self<span style="color:#f92672">.</span>_table[slot] <span style="color:#f92672">is</span> HashTable<span style="color:#f92672">.</span>_DELETED:
                firstSlot<span style="color:#f92672">=</span>slot
            <span style="color:#66d9ef">elif</span> self<span style="color:#f92672">.</span>_table[slot]<span style="color:#f92672">.</span>key<span style="color:#f92672">==</span>key:
                <span style="color:#66d9ef">return</span> (True,slot)
            slot<span style="color:#f92672">=</span>(slot<span style="color:#f92672">+</span>step)<span style="color:#f92672">%</span>len(self<span style="color:#f92672">.</span>_table)
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">_hash1</span>(self,key):
        <span style="color:#66d9ef">return</span> abs(hash(key))<span style="color:#f92672">%</span>len(self<span style="color:#f92672">.</span>_table)
    <span style="color:#66d9ef">def</span> <span style="color:#a6e22e">_hash2</span>(self,key):
        <span style="color:#66d9ef">return</span> <span style="color:#ae81ff">1</span><span style="color:#f92672">+</span>abs(hash(key))<span style="color:#f92672">%</span>(len(self<span style="color:#f92672">.</span>_table)<span style="color:#f92672">-</span><span style="color:#ae81ff">2</span>)
</code></pre></div>
</div>


    </main>

    
  </body>
</html>
